//链表
#include<stdio.h>
#include<stdlib.h>

struct Node{
    int data;
    struct Node* next;
};

struct Node* head=NULL;  //全局变量


void Insert_head(int num){        //链表头插值num
    struct Node* temp=(struct Node*)malloc(sizeof(struct Node));  //C++:Node* temp=new Node();
    temp->data=num;   //(*temp).data=num;
    temp->next=head;  //(*temp).next=head;
    // temp->next=NULL;  
    // if(head!=NULL)temp->next=head;
    head=temp;
}


void Insert(int num,int x){      //链表位置x插入值num
    struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    temp->data=num;    //temp1为创建的表块
    temp->next=NULL;  
    if(x==1){
        temp->next=head;
        head=temp;
    }
    else{
        struct Node* last_temp=head;
        for(int i=1;i<x-1;i++){
            last_temp=last_temp->next;
        }
        temp->next=last_temp->next;
        last_temp->next=temp;
    }
}


void Delete(int x){  //链表位置x删除值
    struct Node* last_temp=head;
    if(x==1){
        head=last_temp->next;;
        free(last_temp);
    }
    else{
        for(int i=1;i<x-1;i++){
            last_temp=last_temp->next;
        }
    }
    struct Node* temp=last_temp->next;
    last_temp->next=temp->next;
    free(temp);     
}


void Reverse1(){ //反转链表 迭代法iterate
    struct Node* current,*prev,*next;
    current=head;
    prev=NULL;
    while(current!=NULL){
        next=current->next;
        current->next=prev; //改地址值
        prev=current;   //移动指针
        current=next;
    }
    head=prev;
}

void Reverse2(struct Node* p){ ////反转链表 递归法recurse
    if(p->next==NULL){
        head=p;
        return;
    }
    Reverse2(p->next);
    struct Node* q=p->next;
    q->next=p;                // p->next->netx=q;
    p->next=NULL;   
}



void Print(){  //打印链表 iterate
    struct Node* temp=head;
    printf("Lits is:");
    while(temp!=NULL){
        printf(" %d",temp->data);
        temp=temp->next;
    }
    printf("\n");
}

void Print_123(struct Node* p){  //顺序打印链表 recurse 递归法实现-函数嵌套
    if(p==NULL){
        printf("\n");
        return;
    }
    printf("%d\t",p->data);
    Print_123(p->next);
}

void Print_321(struct Node* p){  //逆序打印链表 recurse 递归法实现-函数嵌套
    if(p==NULL){
        printf("\n");
        return;
    }
    Print_321(p->next);
    printf("%d\t",p->data);
}


int main(){
    // int num,x;
    // char choose;
    // do{
    //     printf("the operate you choose:add or del?");
    //     scanf(" %c",&choose);

    //     switch (choose){   
    //         case 'a':
    //         int n;
    //         printf("Enter how number you add:");
    //         scanf(" %d",&n);
    //         for(int i=0;i<n;i++){
    //             printf("Enter the number and position:");
    //             scanf(" %d %d",&num,&x);
    //             Insert(num,x);
    //             Print();    
    //         }
    //         break;

    //         case 'd':
    //             printf("Delete the number at:");
    //             scanf(" %d",&x);
    //             Delete(x);
    //             Print();
    //             break;
            
    //         default:
    //             break;
    //     }

    //     printf("-------------------------------\n");
        
    // }while(choose=='a'||choose=='d');
    
    
    // printf("Enter the number:");  //头插法
    // scanf(" %d",&num);
    // Insert_head(num);

    // printf("Enter the number:"); //尾插法
    // scanf(" %d",&num);
    // Insert(num,(i+1));

    
    Insert(1,1);
    Insert(2,2);
    Insert(3,3);
    Insert(4,4);
    Insert(5,5);
    
    // Print_123(head);   //递归法打印测试
    // Print_321(head);

    // Reverse1(head);       //迭代法反转链表测试
    // Print_123(head);

    Reverse2(head);       //递归法反转链表测试
    Print_123(head);

}



